#ifndef Tree_H_INCLUDED
#define Tree_H_INCLUDED
#include <stdlib.h>
#include <iostream>
#include <list>
#include <set>
#include <string>
#include <vector>

template < typename T, typename Allocator = std::allocator<T> >

class Tree
{
    private :
        std::vector<T> _key_list;
        std::vector<Tree<T, Allocator>*> _child_list;        
        Tree<T, Allocator>* _father;
        int _arite;

    public :
		/**
		 *@brief constructeur.
		 *@Param arite de l'arbre, 2 par défaut.
		 */
        Tree(int arite = 2);              
               
		/**
		 *@brief permet de récupérer l'élement le plus grand de la liste de clé _key_list.
		 *@return l'élement le plus grand de la liste de clé _key_list.
		 */
        T max_element();

		/**
		 *@brief permet de récupérer l'élement le plus petit de la liste de clé _key_list.
		 *@return l'élement le plus petit de la liste de clé _key_list.
		 */
        T min_element();

		/**
		 *@brief permet de récupérer le noeud (forcément une feuille) où la clé doit être insérer.
		 *@param T key clé à insérer.
		 *@return le noeud où la clé doit être insérer.
		 */
        Tree<T, Allocator>* find_child_insert(T key);

		/**
		 *@brief permet de récupérer la liste des enfants du noeud courant.
		 *@return la liste des enfants du noeud courant (_child_list).
		 */
        std::vector<Tree<T, Allocator>*> get_child_list();

		/**
		 *@brief permet d'ajouter un noeud à la liste des enfants du noeud courant.
		 *@param Tree Le noeud a ajouter a la liste des enfants (_child_list).
		 */	
        void add_child(Tree<T, Allocator>* Tree);

		/**
		 *@brief permet d'afficher l'arbre
		 *@param os flux de sortie
		 */
        std::ostream& display_child_list(std::ostream& os, std::string separateur);
              
		/**
		 *@brief permet de récupérer la liste des clés du noeud courant.
		 *@return la liste des clés du noeud courant (_key_list).
		 */
        std::vector<T>& get_key_list();

		/**
		 *@brief permet d'ajouter une clé à l'arbre.
		 *@param key La clé à ajouter à l'arbre.
		 */	
        void add_key(T key);

		/**
		 *@brief permet de suprimmer une clé de l'arbre.
		 *@param key La clé à suprimmer de l'arbre.
		 */			
        void remove_key(T key);

		/**
		 *@brief permet d'ajouter une clé à la liste de clé du noeud courant.
		 *@param key La clé à ajouter à la liste de clé (_key_list).
		 */	
        void insert_key(T key);

		/**
		 *@brief Permet de savoir si le noeud placé en paramètre possède une clé inférieur à la clé placé en paramètre.
		 *@param Tree Noeud ou l'on effectue la recherche.
		 *@param key Clé servant de témoin dans la recherche.
		 *@return Vrai si le noeud contient une clé inférieur à celle placé en paramètre. Faux sinon.
		 */	
        bool search_inferior_key (Tree<T, Allocator> * Tree, T key);

		/**
		 *@brief permet de récupérer la clé la plus proche mais inférieur à la clé en paramètre parmi les clés du noeud placés en paramètre.
		 *@param Tree Noeud où l'on recherche la clé la plus proche.
		 *@param key Clé limite.
		 *@return la valeur de la liste des clés la plus proche de key.
		 */	
        T biggest_inferior_key(Tree<T, Allocator> * Tree, T key);
				
		/**
		 *@brief permet de recupérer le père du noeud courant.
		 *@return Le père du noeud courant.
		 */	
		Tree<T, Allocator>* get_father();

		/**
		 *@brief permet d'ajouter ou de modifier le père du noeud courant.
		 *@param Tree Le père du noeud courant.
		 */	
        void add_father(Tree<T, Allocator>* Tree);

		/**
		 *@brief permet de fusionner le noeud courant avec le noeud placé en paramètre
		 *@param Tree Noeud à fusionner au noeud courant.
		 */	  
        void Tree_fusion(Tree<T, Allocator> * Tree);

		/**
		 *@brief permet de trier les clés du noeud courant dans l'ordre croissant.
		 */	  
		void sort_key_list();

		/**
		 *@brief permet de trier les enfants du noeud courant en fonction de leur plus petite clé dans l'ordre croissant.
		 */	
		void sort_child_list();

		/**
		 *@brief permet de suprimmer une clé de la liste des clé du noeud courant.
		 *@param key La clé à suprimmer.
		 */	
		bool remove_key_list(T key);

		/**
		 *@brief permet de transformer une feuille en un noeud avec deux feuilles.
		 */	
		void Tree_split();

		/**
		 *@brief permet de savoir si le noeud courant peut créer des enfants (c'est à dire si le noeud père à atteint le nombre maximal d'enfant.
		 *@param Vrai si le noeud courant (une feuille) peut avoir des enfants.
		 */	
		bool can_create_child();

		/**
		 *@brief premet d'ajouter un frère au noeud courant, en y ajoutant ses valeurs (arite/2) au frère, et sa valeur mediane au noeud père.
		 */	
		void add_brother();

		/**
		 *@brief permet de recupérer le noeud contenant la clé placé en paramètre.
		 *@param key Clé recherché dans les noeuds.
		 *@return Le noeud contenant la clé recherché.
		 */
		Tree<T, Allocator> * search_key(T);

		/**
		 *@brief permet de recupérer le fils gauche du noeud courant
		 */
		Tree<T, Allocator> * find_left_child();

		/**
		 *@brief permet de recupérer le fils droit du noeud courant
		 */
		Tree<T, Allocator> * find_right_child();
	
};

template < typename T, typename Allocator>
std::ostream& operator<<(std::ostream& os,Tree<T, Allocator>& t)
{
	return t.display_child_list(os, "");
}

template < typename T, typename Allocator>
Tree<T, Allocator>::Tree(int arite)
{
    _father = NULL;
    _arite = arite;
}

template < typename T, typename Allocator>
T Tree<T, Allocator>::max_element()
{
    return _key_list.at(_key_list.size()-1);
}

template < typename T, typename Allocator>
T Tree<T, Allocator>::min_element()
{
    return _key_list.at(0);
}

template < typename T, typename Allocator>
Tree<T, Allocator>* Tree<T, Allocator>::find_child_insert(T key)
{
	Tree<T, Allocator> * tmp = NULL;
	if(key <= min_element())
	{	
		if(_child_list.size() == 0)
		{
			return this;
		}
		else
		{
			return _child_list.at(0)->find_child_insert(key);
		}
	}
	else if(key >= max_element())
	{
		if(_child_list.size() == 0)
		{
			return this;
		}
		else
		{
			return _child_list.at(_child_list.size()-1)->find_child_insert(key);
		}
	}
	else
	{
		if(_child_list.size() == 0)
		{
			return this;
		}
		else
		{
			for(int i = 0; i<_child_list.size(); i++)
			{
				//Si la clé mini est inférieur a la clé on test la clé max
				if(_child_list.at(i)->min_element() < key)
				{
					//Si la clé max est inférieur a la clé, alors on verifie pour les autres noeuds
					if(_child_list.at(i)->max_element() < key)
					{
						//Si c'est le dernier noeud a tester, c'est le plus grand
						if(i+1 == _child_list.size())
						{
							return _child_list.at(i)->find_child_insert(key);
						}
						else
						{
							//comme les noeuds sont rangés, pas besoin de sauvegarder une valeur
							tmp = _child_list.at(i);
						}
					}
					else
					//la clé est comprise entre la valeur min et max
					{
						return _child_list.at(i)->find_child_insert(key);
						
					}
				}
				//Si la clé mini est supérieur a la plus petite clé du noeud, on le garde en mémoire ainsi que la clé
				else
				{
					if(i==0)
					{
						return _child_list.at(i)->find_child_insert(key);
					}			
					else
					{
						if(_key_list.at(i-1) < key)
						{
							return _child_list.at(i)->find_child_insert(key);
						}
						else
						{
							tmp->find_child_insert(key);
						}
					}
				}
			}
			if(tmp->get_child_list().size() != 0)
			{
				return tmp->find_child_insert(key);
			}
			else
			{
				return tmp;
			}
		}
	}
}

template < typename T, typename Allocator>
std::vector<Tree<T, Allocator>*> Tree<T, Allocator>::get_child_list()
{
  	return _child_list;
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::add_child(Tree<T, Allocator>* n)
{
    _child_list.push_back(n);
}

template < typename T, typename Allocator>
std::ostream& Tree<T, Allocator>::display_child_list(std::ostream& os,std::string separateur)
{
	os << separateur;
	os << "[";
    for(int i = 0; i<_key_list.size();i++)
    {
		
    	os << _key_list.at(i);
		os << " ";
    }
    os << "]" << std::endl;
	separateur += "    ";
    for(int a = 0; a<_child_list.size(); a++)
    {
        _child_list.at(a)->display_child_list(os, separateur);
    }
	return os;
}

template < typename T, typename Allocator>
Tree<T, Allocator>* Tree<T, Allocator>::get_father()
{
	return _father;
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::add_key(T key)
{
	Tree<T, Allocator> * Tree_to_insert = NULL;
	if(_father == NULL)
	{
		if(_child_list.size() == 0)
		{
			if(_key_list.size() != (_arite*2))
			{
				insert_key(key);
				sort_key_list();
			}
			else
			{
				insert_key(key);
				sort_key_list();
				Tree_split();
			}
		}
		//la racine a deja deux fils
		else
		{
			Tree_to_insert = find_child_insert(key);
			//Si le noeud est deja plein
			if(Tree_to_insert->get_key_list().size() == 2*_arite )
			{
				//Si la racine n'a pas atteint le nombre max de fils
				if(_child_list.size() < ((_arite*2)+1))
				{
					Tree_to_insert->insert_key(key);
					Tree_to_insert->sort_key_list();
					Tree_to_insert->add_brother();
				}
				else
				{
					Tree_to_insert->add_key(key);
					Tree_to_insert->sort_key_list();
				}
			}
			//le noeud n'est pas plein
			else
			{
				Tree_to_insert->insert_key(key);
				Tree_to_insert->sort_key_list();
			}
		}
	}
	else
	//Ce n'est pas la racine
	{
		insert_key(key);
		sort_key_list();
		if(get_father()->get_child_list().size() == ((_arite*2)+1))
		{
			Tree_split();
		}
		else
		{
			add_brother();
		}
	}
}
   
template < typename T, typename Allocator>
void Tree<T, Allocator>::remove_key(T key)
{
	
	T key_deleted = key; //Besoin de connaitre cette valeur pour les deux étapes de réordonnacement
	Tree<T, Allocator>* noeud_Key = search_key(key);

	noeud_Key->remove_key_list(key);
	
	Tree<T, Allocator>* fils_droit = noeud_Key->find_right_child();
	Tree<T, Allocator>* fils_gauche = noeud_Key->find_left_child();
	//Si le nombre de clé est inférieur a l'arite
	if (noeud_Key->get_key_list().size() < _arite && _father != NULL)
	{
		//si le fils droit a suffisamment de place pour accueillir toutes les clés
	
		if (fils_droit != NULL && fils_droit->get_key_list().size() < (2*_arite))
		{
			//on ajoute la médiane du noeud père entre fils droit et noeud courant au fils droit
			_father->get_key_list().back();
			T big_inf_key = biggest_inferior_key(_father, fils_droit->min_element());
			fils_droit->get_key_list().push_back(big_inf_key);

				//on ajoute les valeurs au fils droit sauf la derniere, qu'on ajoute au père
			int i ;
			for (i = 0; i < noeud_Key->get_key_list().size(); i ++)
			{
				if (i != noeud_Key->get_key_list().size()-1)
				{
					fils_droit->get_key_list().push_back(noeud_Key->get_key_list().at(i));
				}
				else
				{
					_father->get_key_list().push_back(noeud_Key->get_key_list().at(i));
				}					
			}
		}
		else
		{
			if (fils_gauche != NULL)
			{		
				//on ajoute la médiane du noeud père entre fils gauche et noeud courant au fils gauche
				_father->get_key_list().back();
				T big_inf_key = biggest_inferior_key(_father, fils_gauche->max_element());
				fils_gauche->get_key_list().push_back(big_inf_key);
				//on ajoute les valeurs au fils gauche sauf la derniere, qu'on ajoute au père
				for (int i = 0; i < noeud_Key->get_key_list().size(); i ++)
				{
					if (i != noeud_Key->get_key_list().size()-1)
					{
						fils_gauche->get_key_list().push_back(noeud_Key->get_key_list().at(i));
					}
					else
					{
						_father->get_key_list().push_back(noeud_Key->get_key_list().at(i));
					}					
				}
			}
		}
	}
	else
	{
			// sinon si nb clé fils droit + nb clé fils gauche <= (2*(arite*2) - nb cle noeud courant
		if ( fils_droit != NULL && _father != NULL && fils_gauche != NULL && (fils_droit->get_key_list().size() + fils_gauche->get_key_list().size()) <=  (2*_arite*2)-_key_list.size())
		{
			//tant que nombre de clé de fils droit < 2arite && il y a des clés dans le noeud courant
			while(fils_droit->get_key_list().size() < (2*_arite) && _key_list.size() > 0)
			{
				//on y insère la clé mediane du père (entre max fils droit et min noeud courant)
				T big_inf_key = biggest_inferior_key(_father, fils_droit->min_element());
				fils_droit->get_key_list().push_back(big_inf_key);
				//on insère min noeud courant dans le père
				_father->get_key_list().push_back(this->min_element());						
			}
			//si le fils droit est plein, meme boucle mais pour fils gauche
			if (fils_droit->get_key_list().size() == (2*_arite))
			{
				while(fils_gauche->get_key_list().size() < (2*_arite) && _key_list.size() > 0)
				{
					T big_inf_key = biggest_inferior_key(_father, fils_gauche->max_element());
					fils_gauche->get_key_list().push_back(big_inf_key);
					_father->get_key_list().push_back(this->min_element());	
				}		
			}
		}
		else
		{
			if(_father != NULL)//on pique une clé au fils qui en a au moins arite +1 que l'on met dans le père
			{				
				if ( fils_droit != NULL && fils_droit->get_key_list().size() >= (_arite+1) )
				{
					//on recupère la mediane dans notre noeud
					_father->get_key_list().push_back(fils_droit->get_key_list().back());
					T big_inf_key = biggest_inferior_key(_father, fils_droit->min_element());
					this->_key_list.push_back(big_inf_key);
				}
				else
				{
					if( fils_gauche != NULL && fils_gauche->get_key_list().size() >= (_arite+1) )
					{
						_father->get_key_list().push_back(fils_gauche->get_key_list().back());
						T big_inf_key = biggest_inferior_key(_father, fils_gauche->max_element());
						this->_key_list.push_back(big_inf_key);
					}
				}
			}
		}
	}
	if(fils_droit == NULL && fils_gauche == NULL && noeud_Key->get_father() == NULL && noeud_Key->get_child_list().size() != 0)
	{
		bool end = false;
		while(noeud_Key->get_child_list().size() != 0 && !end)
		{		
			end = true;
			if(noeud_Key->get_child_list().at(0)->get_key_list().size() > (_arite+1))
			{
				noeud_Key->insert_key(noeud_Key->get_child_list().at(0)->max_element());
				noeud_Key->get_child_list().at(0)->remove_key_list(noeud_Key->get_child_list().at(0)->max_element());
				noeud_Key = noeud_Key->get_child_list().at(0);
				end = false;
			}
			else if(noeud_Key->get_child_list().at(1)->get_key_list().size() > (_arite+1))
			{
				noeud_Key->insert_key(noeud_Key->get_child_list().at(1)->max_element());
				noeud_Key->get_child_list().at(1)->remove_key_list(noeud_Key->get_child_list().at(1)->max_element());
				noeud_Key = noeud_Key->get_child_list().at(1);
				end = false;
			}
		}
	}
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::insert_key(T key)
{
    _key_list.push_back(key);
}

template < typename T, typename Allocator>
bool Tree<T, Allocator>::search_inferior_key (Tree<T, Allocator> * Tree, T key)
{
	bool flag_inferior = false;
	T big_infe_Key = biggest_inferior_key(Tree, key);
	if (big_infe_Key != 0)
	{
		flag_inferior = true;
	}
	return flag_inferior;
}

template < typename T, typename Allocator>
T Tree<T, Allocator>::biggest_inferior_key(Tree<T, Allocator> * Tree, T key)
{
	T inferior_key = NULL;
	std::vector<T> _key_listsn = Tree->get_key_list();
	for(int i = 0 ;i < _key_listsn.size(); i++)
	{
		if (_key_list.at(i) < key)
		{
			inferior_key = _key_list.at(i);
		}
	}
	return inferior_key;	
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::add_father(Tree<T, Allocator>* Tree)
{
    _father = Tree;
}

template < typename T, typename Allocator>
std::vector<T>& Tree<T, Allocator>::get_key_list()
{
    std::vector<T>& ref_get_key_list = _key_list;
    return ref_get_key_list;
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::Tree_fusion(Tree<T, Allocator>* Tree)
{
	for(int i = 0;i < Tree->get_child_list().size(); i++)
	{
		add_child(Tree->get_child_list().at(i));
	}	

	for(int a = 0 ;a < Tree->get_key_list().size(); a++)
	{
		add_key(Tree->get_key_list().at(a));
	}	
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::sort_key_list()
{
	T temporary_key;
	int i, j;

	for(i = 0; i < _key_list.size(); i ++)
	{
		for(j = 0; j < _key_list.size(); j ++)
		{
			if (_key_list.at(i) < _key_list.at(j))
			{
				temporary_key = _key_list.at(j);
				_key_list.at(j) = _key_list.at(i);
				_key_list.at(i) = temporary_key;
			}
		}
	}
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::sort_child_list()
{
	Tree<T, Allocator>* temporary_Tree;
	int i, j;
	for(i = 0; i < _child_list.size(); i ++)
	{
		for(j = 0; j < _child_list.size(); j ++)
		{
			if (_child_list.at(i)->min_element() < _child_list.at(j)->min_element())
			{
				temporary_Tree = _child_list.at(j);
				_child_list.at(j) = _child_list.at(i);
				_child_list.at(i)= temporary_Tree;
			}
		}
	}
}

template < typename T, typename Allocator>
bool Tree<T, Allocator>::remove_key_list(T key)
{
	typename std::vector<T>::iterator it;
	for(it = _key_list.begin(); it != _key_list.end(); it++)
	{
		if(*it == key)
		{
			_key_list.erase(it);
			return true;
		}
	}
	return false;
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::Tree_split()
{
	int i =0;
	Tree<T, Allocator>* n = new Tree(_arite);
	while(i<_arite)
	{
       	n->insert_key(min_element());
       	remove_key_list(min_element());
		i++;
	}
	n->sort_key_list();
    add_child(n);
	sort_child_list();
    n->add_father(this);

    Tree<T, Allocator>* n2 = new Tree(_arite);
	i = 0;
	while(i<_arite)
	{
	    n2->insert_key(max_element());
	    remove_key_list(max_element());
		i++;
	}
	n2->sort_key_list();
    add_child(n2);
	sort_child_list();
    n2->add_father(this);
}

template < typename T, typename Allocator>
bool Tree<T, Allocator>::can_create_child()
{
	return get_father()->get_child_list().size() == ((_arite*2)+1);
}

template < typename T, typename Allocator>
void Tree<T, Allocator>::add_brother()
{
	Tree<T, Allocator>* n = new Tree(_arite);
	//on insère la moitié des plus petites valeurs
	int i = 0;
	while(i < _arite)
	{
		n->insert_key(min_element());
		remove_key_list(min_element());
		i++;
	}
	get_father()->add_child(n);
	get_father()->sort_child_list();
	n->add_father(get_father());
	n->sort_key_list();

	//ajout de la clé mediane au père
	get_father()->insert_key(min_element());
	get_father()->sort_key_list();
	remove_key_list(min_element());
}

template < typename T, typename Allocator>
Tree<T, Allocator> * Tree<T, Allocator>::search_key(T key)
{
	typename  std::vector<Tree<T, Allocator> *>::iterator cit;
	typename std::vector<T>::iterator it;
	
	for(it = _key_list.begin(); it != _key_list.end();it++)
	{
		if (key == *it)
		{
			return this;
		}						
	}
	for(cit = _child_list.begin(); cit != _child_list.end();cit++)
	{		
		Tree<T, Allocator> * Tree = *cit;
		if(key>= Tree->min_element() && key<= Tree->max_element())	
		{
			return Tree->search_key(key);
		}
		
	}
	return NULL;
}

template < typename T, typename Allocator>
Tree<T, Allocator> * Tree<T, Allocator>::find_right_child()
{
	Tree  * fils_droit = NULL;
	if(_father != NULL)
	{	
		//Parcours de la liste et retour du noeud precedent
		typename std::vector<Tree<T, Allocator>*>::iterator it;
		for( it= _child_list.begin(); it != _child_list.end();++it)
		{
			Tree<T, Allocator> * Tree = *it;
			if (Tree->get_key_list().at(0)>_key_list.back())
				{
					fils_droit = *it;
				}
		}
	}
	return fils_droit;
}

template < typename T, typename Allocator>
Tree<T, Allocator> * Tree<T, Allocator>::find_left_child()
{

	Tree  * fils_gauche = NULL;
	if(_father != NULL)
	{	
		//Parcours de la liste et retour du noeud precedent
		typename std::vector<Tree<T, Allocator>*>::iterator it;
		for(it = _child_list.begin(); it != _child_list.end();++it)
		{
			Tree<T, Allocator> * Tree = *it;
			if (Tree->get_key_list().back()<_key_list.at(0))
			{
				fils_gauche = *it;
			}
		}
	}
	return fils_gauche;
}

#endif


